package com.datastructures2.search;

import com.datastructures2.背包队列栈.Queue;
import com.sun.org.apache.xpath.internal.functions.FuncFalse;
import edu.princeton.cs.algs4.RedBlackBST;

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * @author MaoLin Wang
 * @date 2020/3/213:41
 */
public class RedBlackTree<Key extends Comparable<Key>,Value> {
    public static void main(String[] args) {
        RedBlackBST<String,Object> tree = new RedBlackBST<>();
       /* Random random=new Random();
        long start=System.currentTimeMillis();

        long end=System.currentTimeMillis();
        System.out.println("插入800W数据时间："+(end-start));*/
        Random random=new Random();
        for (int i = 0; i < 1000000; i++) {
            tree.put(random.nextInt(1000000)+"",1);

        }
        tree.delete("1231");
        tree.delete("3463");
        tree.delete("345674");
        tree.delete("345411");
    }
    private static final boolean RED=true;
    private static final boolean BLACK= false;

    private Node root;

    private class Node{
        private Node left,right;
        /**
         * 其父节点指向该节点的链接颜色
         */
        private boolean color;
        private Key key;
        private Value value;
        /**
         * 子树中的节点总数
         */
        private int size;

        public Node( boolean color,Key key,Value value, int size) {
            this.key=key;
            this.color = color;
            this.value = value;
            this.size = size;
        }

    }

    /**
     * 获取给定键的值
     * @param key
     * @return
     */
    public Value get(Key key){
        if (key==null){
            return null;
        }
        return get(root,key);
    }

    /**
     * 删除最小值
     * 1.当前节点的左孩子是3-节点，过
     * 2.当前节点的左孩子是2-节点，但是兄弟节点是3-节点，此时可以向兄弟节点借一个过来，保证自己不是2-节点；
     * 3.当前节点左孩子右孩子都是2-节点，则向父节点借一个，并将借的节点和左孩子右孩子合并。
     */
    public void  delMin(){
        if (isEmpty()){
            throw new NoSuchElementException("树为空");
        }
        if(!isRed(root.left) && !isRed(root.right)){
            root.color = RED;   // 如果根节点的左右子节点是2-节点，我们可以将根设为红节点，这样才能进行后面的moveRedLeft操作，因为左子要从根节点借一个
        }
        root = delMin(root);
        root.color = BLACK;  // 借完以后，我们将根节点的颜色复原
    }

    private Node delMin(Node node) {
        if (node.left==null){
            return null;
        }
        if (!isRed(node.left) && !isRed(node.left.left)){// 判断node的左节点是不是2-节点
            node=moveRedLeft(node);
        }
        node.left=delMin(node.left);
        return balance(node); //   平衡临时组成的4-节点
    }
    private Node balance(Node node){
        if (isRed(node.right)) {

            node = rotateLeft(node);
        }
        if (isRed(node.right) && !isRed(node.left)) {
            node=rotateLeft(node);
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node=rotateRight(node);
        }
        if (isRed(node.left) && isRed(node.right))  {
            flipColors(node);
        }
        node.size = size(node.left)+size(node.right)+1;
        return node;
    }
    private Node moveRedLeft(Node node) {
        /**
         * 因为我们规定红链接只能在左，
         * 因此当前节点的左右子节点都是2-节点，这时候我们就需要通过颜色转换，将这三个节点合并在一起
         */
        flipColors(node);
        //如果兄弟节点为2-节点的话，那么到上一步就结束了

        if(isRed(node.right.left)){     // 而如果兄弟节点不是2-节点的话，我们就需要通过旋转从兄弟节点借一个过来
            node.right = rotateRight(node.right);
            node = rotateLeft(node);
            //  因为条件2要求我们只向兄弟节点借一个，
            //  而一开始从父节点那里借了一个，因此需要还一个给父节点
            flipColors(node);
        }
        return node;

    }

    /**
     * 删除最大值
     */
    public void delMax(){
        if (isEmpty()){
            throw new NoSuchElementException("树为空");
        }
        if (!isRed(root.left) && !isRed(root.right)){
            root.color=RED;
        }
        root=delMax(root);
        root.color=BLACK;
    }
    private Node delMax(Node node) {
        if(isRed(node.left)){
           /*
                这里需要判断左连接是否为红色，因为最大值要么不存在子孩子，要么最多存在一个左链接
                如果有左红链接，则应该将此节点右旋转，让最大值没有一个孩子，这样就可以直接删除，否则会破坏树的结构，丢失该左孩子
            */
            node = rotateRight(node);
        }
        if (node.right==null){
            return null;
        }
        if (!isRed(node.right) && !isRed(node.right.left)){
            node=moveRedRight(node);
        }
        node.right=delMax(node.right);
        return balance(node);
    }

    private Node moveRedRight(Node node) {
        flipColors(node);
        if (isRed(node.left.left)){
            node=rotateRight(node);
            flipColors(node);
        }
        return node;
    }
    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to delete() is null");
        if (!contains(key)) return;

        if (!isRed(root.left) && !isRed(root.right))
            root.color = RED;


        root = delete(root, key);
        System.out.println("删除:"+key+"旋转"+count+"次，换色:"+flipCount+"次");
        count=0;
        if (!isEmpty()) root.color = BLACK;
    }
    private Node delete(Node node, Key key) {

        if (key.compareTo(node.key) < 0)  {
            //key在左子树，按删除最小值一样删除
            if (!isRed(node.left) && !isRed(node.left.left))
                node = moveRedLeft(node);
            node.left = delete(node.left, key);
        }
        else {//key在右子树，按删除最大值一样删除
            if (isRed(node.left))
                node = rotateRight(node);
            //需首先判断待删除的节点是否在树底，否则下一步的node.right.left会出现空指针
            if (key.compareTo(node.key) == 0 && (node.right == null))
                return null;
            //递归在右子树中删除
            if (!isRed(node.right) && !isRed(node.right.left))
                node = moveRedRight(node);
            //如果待删除的节点不在树底
            if (key.compareTo(node.key) == 0) {
                //像二叉查找树一样删除，从node右子树找到最小的节点放在当前位置，然后再将该最小节点从右子树删除
                Node x = min(node.right);
                node.key = x.key;
                node.value = x.value;

                node.right = delMin(node.right);
            }
            else {
                //key仍然大于该node，继续在右子树递归
                node.right = delete(node.right, key);
            }
        }
        return balance(node);
    }

    /**
     * 返回最小的键
     * @return
     */
    public Key min() {
        if (isEmpty()) throw new NoSuchElementException("called min() with empty symbol table");
        return min(root).key;
    }
    private Node min(Node x) {
        if (x.left == null) return x;
        else                return min(x.left);
    }

    /**
     * 返回最大的键
     * @return
     */
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("called max() with empty symbol table");
        return max(root);
    }

    private Key max(Node node) {
        return node==null?node.key:max(node.right);
    }
    public int height(){
        return height(root);
    }

    private int height(Node node) {
        if (node==null){
            return -1;
        }
        return 1+Math.max(height(node.left),height(node.right));
    }

    public Key floor(Key key){
        if (key == null) throw new IllegalArgumentException("argument to floor() is null");
        if (isEmpty()) throw new NoSuchElementException("called floor() with empty symbol table");
        Node x = floor(root, key);
        if (x==null){
            return null;
        }else {
            return x.key;
        }
    }

    /**
     * 向下取整
     * @param node
     * @param key
     * @return
     */
    private Node floor(Node node, Key key) {
        if (node==null){
            return null;
        }
        int cmp=key.compareTo(node.key);
        if (cmp==0){
            return node;
        }else if (cmp<0){
            return floor(node.left,key);
        }else {
            Node t = floor(node.right, key);
            if (t != null) return t;
            else           return node;
        }


    }

    /**
     * 向上取整
     * @param key
     * @return
     */
    public Key ceiling(Key key) {
        if (key == null) throw new IllegalArgumentException("argument to ceiling() is null");
        if (isEmpty()) throw new NoSuchElementException("called ceiling() with empty symbol table");
        Node x = ceiling(root, key);
        if (x == null) return null;
        else           return x.key;
    }

    private Node ceiling(Node node, Key key) {
        if (node==null){
            return null;
        }
        int cmp=key.compareTo(node.key);
        if (cmp==0){
            return node;
        } else if (cmp<0){
            Node t=ceiling(node.left,key);
            if (t==null){
                //左子树未找到 则返回当前节点
                return node;
            }else {
                //左子树找到该key，直接返回对应的node
                return t;
            }
        }else{
            return floor(node.right,key);
        }
    }

    /**
     * 返回从小到大第k个key
     * @param k
     * @return
     */
    public Key select(int k){
        if (k<0 || k>=size(root)){
            throw new IllegalArgumentException("called select() with invalid argument: " + k);
        }
        Node x = select(root, k);
        return x.key;
    }

    private Node select(Node node, int k) {
        int t = size(node.left);
        if (t<k){
            return select(node.right,k-t-1);
        }else if (t>k){
            return select(node.left,k);
        }else {
            return node;
        }
    }
    public Iterable<Key> keys() {
        if (isEmpty()) return new Queue<Key>();
        return keys(min(), max());
    }
    public Iterable<Key> keys(Key lo, Key hi) {
        if (lo == null) throw new IllegalArgumentException("first argument to keys() is null");
        if (hi == null) throw new IllegalArgumentException("second argument to keys() is null");

        Queue<Key> queue = new Queue<Key>();
        keys(root, queue, lo, hi);
        return queue;
    }
    private void keys(Node x, Queue<Key> queue, Key lo, Key hi) {
        if (x == null) return;
        int cmplo = lo.compareTo(x.key);
        int cmphi = hi.compareTo(x.key);
        if (cmplo < 0){
            keys(x.left, queue, lo, hi);
        }
        if (cmplo <= 0 && cmphi >= 0) {
            queue.enqueue(x.key);
        }
        if (cmphi > 0){
            keys(x.right, queue, lo, hi);
        }
    }



    /**
     * 获取给定键值
     * @param node
     * @param key
     * @return
     */
    private Value get(Node node, Key key) {
        while (node!=null){
            int result=key.compareTo(node.key);
            if (result<0){
                node=node.left;
            }else if (result>0){
                node=node.right;
            } else {
                return node.value;
            }
        }
        return null;
    }

    int count=0;
    int flipCount=0;
    /**
     * 插入一个值
     * @param value
     */
    public void put(Key key,Value value){
        if (key == null) throw new IllegalArgumentException("key为空");
        if(value==null){
            delete(key);
            return;
        }

        root=put(root,key,value);
        System.out.println(key+": 进行了"+count+"次旋转,"+flipCount+"次换色");
        count=0;
        flipCount=0;
        //插入后将根节点颜色变为黑色
        root.color=BLACK;
    }
    /**
     * 是否存在给定键
     * @param key
     * @return
     */
    public boolean contains(Key key){
        return get(key)!=null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 插入一个值
     * @param node
     * @param value
     * @param key
     * @return
     */
    private Node put(Node node,Key key,Value value) {
        if (node==null){
            //插入的节点，总是让它的颜色初始化为红
            return new Node(RED,key,value,1);
        }
        int result=key.compareTo(node.key);
        if (result<0){
            node.left=put(node.left,key,value);
        }else if (result>0){
            node.right=put(node.right,key,value);
        }else {
            node.value=value;
        }


        /*
            右链接为红色
            1.即向2-节点右边插入
            2 或是 向3-节点中间插入
         */
        if (isRed(node.right)&&!isRed(node.left)){
            count++;
            //左旋转
            node=rotateLeft(node);
        }
        //3.指向新节点的链接为3-节点的左链接
        //4.或是情况2左旋转后的状态
        if (isRed(node.left)&&isRed(node.left.left)){
            count++;
            //右旋转
            node=rotateRight(node);
        }
        //5.左右链接均为红，即成为一个4-节点(3、4 右旋转后的状态)
        if (isRed(node.left)&&isRed(node.right)){
            flipCount++;
            //转换颜色
            flipColors(node);
        }
        node.size=size(node.left)+size(node.right)+1;
        return node;
    }


    /**
     * 是否被红链接指向
     * @param node
     * @return
     */
    private boolean isRed(Node node){
        return node==null?false:node.color;
    }

    /**
     * 左旋转(右链接为红色)
     * @param node
     * @return
     */
    private Node rotateLeft(Node node){

        count++;
        Node right=node.right;
        node.right=right.left;
        right.left=node;

        right.color=node.color;
        node.color=RED;

        right.size=node.size;
        node.size=1+size(node.left)+size(node.right);
        return right;
    }

    /**
     * 右旋转(左链接为红色)
     * @param node
     * @return
     */
    private Node rotateRight(Node node){

        count++;
        Node left=node.left;
        node.left=left.right;
        left.right=node;

        left.color=node.color;
        node.color=RED;

        left.size=node.size;
        node.size=1+size(node.left)+size(node.right);
        return left;
    }

    /**
     * 颜色转换  父节点变为红色，两个子节点变为黑色
     * @param node
     */
    private void flipColors(Node node){
        flipCount++;
        node.color = !node.color;
        node.left.color = !node.left.color;
        node.right.color = !node.right.color;
    }
    /**
     * 返回当前节点的子树节点总数
     * @param node
     * @return
     */
    private int size(Node node) {
        return node==null?0:node.size;
    }

}
